#include <dbg.h>
#include <gtest/gtest.h>

#include <climits>

using namespace std;

#ifdef PREORDER_TRAVERSAL  // 前序遍历
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return dfs(root, INT_MIN, INT_MAX);  // 初始范围为 (INT_MIN, INT_MAX)
    }

private:
    bool dfs(TreeNode* root, int left, int right) {
        if (root == nullptr) {  // 空树也是二叉搜索树
            return true;
        }
        int val = root->val;
        if (val <= left ||
            val >= right) {  // 如果当前节点的值不在范围内, 则不是二叉搜索树
            return false;
        }
        return dfs(root->left, left, val) &&
               dfs(root->right,
                   val,
                   right);  // 递归判断左右子树, 左子树更新右边界,
                            // 右子树更新左边界
    }
};
#endif

#ifdef INORDER_TRAVERSAL  // 中序遍历
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        int pre = INT_MIN;  // 初始化前一个节点值为最小值
        return dfs(root, pre);
    }

private:
    bool dfs(TreeNode* root, int& pre) {
        if (root == nullptr) {  // 空树也是二叉搜索树
            return true;
        }
        if (!dfs(root->left,
                 pre)) {  // 左子树, 如果不是二叉搜索树, 则返回 false
            return false;
        }
        if (root->val <=
            pre) {  // 如果当前节点的值小于等于前一个节点的值, 则不是二叉搜索树
            return false;
        }
        pre = root->val;               // 更新前一个节点的值
        return dfs(root->right, pre);  // 递归右子树
    }
};
#endif

#ifndef POSTORDER_TRAVERSAL  // 后序遍历
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        auto [minVal, maxVal] = dfs(root);
        return minVal != INT_MIN ||
               maxVal != INT_MAX;  // 若返回的最大值和最小值正常，则为二叉搜索树
    }

private:
    pair<long long, long long> dfs(TreeNode* root) {
        if (root ==
            nullptr) {  // 空树， 返回 (LLONG_MAX, LLONG_MIN) 特殊值，表示有效
            return {LLONG_MAX, LLONG_MIN};
        }

        auto [leftMin, leftMax] = dfs(root->left);     // 递归左子树
        auto [rightMin, rightMax] = dfs(root->right);  // 递归右子树

        long long val = root->val;
        if (val <= leftMax ||
            val >= rightMin) {  // 如果当前节点的值不在范围内, 则不是二叉搜索树
            return {LLONG_MIN, LLONG_MAX};
        }
        return {min(leftMin, val),
                max(rightMax, val)};  // 返回左子树的最小值和右子树的最大值
    }
};
#endif

TEST(isValidBST, TestCase1) {
    Solution s;

    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);

    EXPECT_EQ(s.isValidBST(root), true);
}

TEST(isValidBST, TestCase2) {
    Solution s;

    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->right->left = new TreeNode(3);
    root->right->right = new TreeNode(6);

    EXPECT_EQ(s.isValidBST(root), false);
}

TEST(isValidBST, TestCase3) {
    Solution s;

    TreeNode* root = new TreeNode(2147483647);

    EXPECT_EQ(s.isValidBST(root), true);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}